#ifndef _BPLUSTREE_
#define _BPLUSTREE_
#include <string>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <memory>
#include "buffermanager.h"
#include "block.h"
#include "UserCommand.h"
#include "data.h"

typedef struct BplusNode *PBplusNode;
struct BplusNode{
	int block_num;
	bool dirty;
	bool isleaf;
	std::list<Data> nums;
	PBplusNode parent;
	std::list<PBplusNode> children;
	std::list<int> block_nums;
	inline void setDirty()
	{
		if (dirty)
			dirty = true;
	}

};

class BplusTree
{
public:
	//supports "char", "int", "float"
	BplusTree(std::string table_name, std::string type, int data_len, std::string index_name, 
		std::string attr_name, int head_block, int index_block_num, std::shared_ptr<BufferManager> buffer_manager, std::vector<bool> &empty_table, bool has_setup);
	void Insert(Data data, int line_num);
	void Delete(Data data, int line_num);
	void DropTree();
	void Save();//save the tree to buffer
	int getHeadBlock()const;
	int getIndexBlock()const;
	std::string getIndexName() const;
	std::string getAttrName() const;
	std::string getType() const;
	int getLen() const;
	std::set<int> select(Condition cond);
	void PrintTree();
	virtual ~BplusTree();
private:
	PBplusNode head;
	PBplusNode createNode(PBplusNode pa);
	PBplusNode createNode(PBplusNode pa, int head_block);
	// release the space created for node;
	void releaseNode(PBplusNode node);
	bool insertLeaf(PBplusNode leaf, Data data);
	//deepth-first search to print the b+tree, for debug
	void printTree(PBplusNode head, int level);
	// insert child into node, and if child is a internal node, 
	//remove its first keyword
	void insertNode(PBplusNode node, PBplusNode child);
	bool deleteLeaf(PBplusNode leaf, Data data);
	//delete child from node, if child is an internal node, 
	//give the keyword back to it
	void deleteNode(PBplusNode node, PBplusNode child);
	//find the leaf that contains the data
	PBplusNode findLeaf(PBplusNode head, Data data);
	//find the leftest leaf in the b+ tree;
	PBplusNode findFirstLeaf(PBplusNode head);
	//split half of the src' children to des
	void split(PBplusNode src, PBplusNode des);
	//merge the src to the des
	void merge(PBplusNode des, PBplusNode src);
	//replace data with des
	void updateNode(PBplusNode leaf, Data data, Data des);
	//find a sibling that can be used for deleting a node
	//or fit the node by transfer a keyword from sibling, 
	//node should have a parent
	PBplusNode findSibling(PBplusNode node);

	//find an empty place in index block to store the infomation;
	int findEmptyIndexLocation();
	PBplusNode createNodeFromBlock(Block block, PBplusNode pa);
	void writeNodeToBlock(PBplusNode node, Block &block);
	unsigned int order;
	std::string file_name;
	std::string type;
	std::string index_name;
	std::string attr_name;
	int data_len;
	int index_block_num;
	bool has_setup;
	std::shared_ptr<BufferManager> buffer_manager;
	std::vector<bool> &empty_table;
	std::map < Data, std::set<int> > index_map;
};

#endif
